import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
// https://leetcode.cn/problems/word-break/submissions/431427777/
class wordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean [] dp = new boolean[len+1];
        HashSet<String> set = new HashSet<>();
        for(String str : wordDict)
        {
            set.add(str);
        }
        Arrays.fill(dp,false);
        dp[0] = true;
        for(int i = 1 ; i <= len ; i ++)
        {
            for(int j = 0 ; j < wordDict.size() ; j ++)
            {
                int size = wordDict.get(j).length();
                if(size <= i){
                    String sub = s.substring(i-size,i);
                    if(set.contains(sub) && dp[i - size])
                    {
                        dp[i] = true;
                    }
                }
            }
        }
        return dp[len];



    }
}